#ifndef KDTREE
#define KDTREE

#include "GM3Graph.h"   //#include "GM3Graph.h"
#include "cvec.h"

#include <vector>

//namespace GM3{

class KDTree
{
    public:
        struct boundingBox{
            cvec ll; //lower left corner
            cvec ur; //upper right corner
            boundingBox(cvec p0 = cvec(), cvec p1 = cvec(1.f,1.f))
            { ll = p0; ur = p1; }
        };
        struct node{
            unsigned int s, t;
            node *l, *r; //left and right children
            cvec p; //center of the cell
            float d; //distance to furthest node
            float w; //combined weight of both subtrees

            float m; //FIXME: not really needed
            boundingBox bb; //FIXME: doesn't need to be stored, either

            node(unsigned int s0 = 0, unsigned int t0 = 0, cvec p0=cvec(),
                    float d0=0.f, node *l0=0, node *r0=0)
            { s = s0; t = t0; p = p0; d = d0; l = l0; r = r0; m = 0.f; }
        };

        KDTree();
        KDTree(GM3Graph *);
        ~KDTree();

        inline unsigned int size(){ return treeSize; }
        inline unsigned int height(){ return treeHeight; }
        inline unsigned int leaves(){ return numLeaves; }
        inline unsigned int avgLeaf(){ return avgLeafSize; }
        inline unsigned int maxLeaf(){ return maxLeafSize; }

        inline GM3Graph *graph(){ return G; }
        inline void graph(GM3Graph *g){ G = g; }

        static inline unsigned int threshold(){ return thresh; }
        static inline void threshold(unsigned int t){ thresh = t; } //rebuild?

        inline node *kdroot(){ return root; }

        //NOTE: this will renumber the nodes of the graph
        // both versions return a translation vector. For each node i, vector[i]
        // stores the new position of i
        std::vector<unsigned int> buildTree();
        std::vector<unsigned int> buildTree(unsigned int);

        void translateEdges(std::vector<unsigned int> &);
        void translateParents(std::vector<unsigned int> &);

        node *findLeaf(float x, float y);
    private:
        static const unsigned int pivotSpaceSize = 20;
        static unsigned int thresh;

        GM3Graph *G;
        node *root;
        unsigned int treeSize;
        unsigned int treeHeight;
        unsigned int numLeaves;
        float avgLeafSize;
        unsigned int maxLeafSize;

        //recursively free all nodes
        void freeKDTree(node *);

        //calculate information about a set of graph nodes
        cvec findCenter(std::vector<unsigned int>::iterator s,
                std::vector<unsigned int>::iterator t);
        float findRadius(std::vector<unsigned int>::iterator s,
                std::vector<unsigned int>::iterator t, cvec c);
        float sumWeight(std::vector<unsigned int>::iterator s,
                std::vector<unsigned int>::iterator t);

        //recuresively build the tree
        node *buildSubTree(std::vector<unsigned int>::iterator first,
                std::vector<unsigned int>::iterator s,
                std::vector<unsigned int>::iterator t,
                unsigned int depth, unsigned int thresh, boundingBox bb);

        //select a set of radices
        std::vector<GM3Graph::node> pivotSet(std::vector<unsigned int>::iterator s,
                std::vector<unsigned int>::iterator t);
        float medianX(std::vector<unsigned int>::iterator s,
                std::vector<unsigned int>::iterator t);
        float medianY(std::vector<unsigned int>::iterator s,
                std::vector<unsigned int>::iterator t);

        //sort the sub array around the median
        std::vector<unsigned int>::iterator pivotSortX(
                std::vector<unsigned int>::iterator s,
                std::vector<unsigned int>::iterator t, float median);
        std::vector<unsigned int>::iterator pivotSortY(
                std::vector<unsigned int>::iterator s,
                std::vector<unsigned int>::iterator t, float median);
};

//}

#endif
